package leetcode;

public class LC34 {
    public static void main(String[] args) {
        LC34 lc34 = new LC34();
        ListNode.print(lc34.mergeKLists(new ListNode[]{ListNode.ln(new int[]{1,4,5}),ListNode.ln(new int[]{1,3,4}),ListNode.ln(new int[]{2,6})}));
    }
    /*
        不同解法：
            1.顺序合并
            2.两两分组递归合并
     */
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) return null;
        if (lists.length == 1) return lists[0];
        ListNode ans = new ListNode(0);
        ListNode temp = null;
        ListNode next = null;
        int i = 0;
        while(i != -1){
            i = -1;
            for (int j = 0; j < lists.length; j++) {
                ListNode node = lists[j];
                if (node == null){
                    continue;
                }
                if (temp == null || temp.val > node.val) {
                    temp = node;
                    i = j;
                }
            }
            if (i < 0) continue;
            if (next == null) {
                next = temp;
                ans.next = next;
            }else {
                next.next = temp;
                next = temp;
            }
            lists[i] = lists[i].next;
            temp = null;
        }
        return ans.next;
    }
}
